#include <stdio.h>
#include <stdlib.h>

//链表中的节点结构
typedef struct linkQueue {
    int data;
    struct linkQueue * next;
}linkQueue_t;

//创建链式队列的函数
linkQueue_t * initQueue() {
    //创建一个头节点
    linkQueue_t * head = (linkQueue_t *)malloc(sizeof(linkQueue_t));
    //对头节点进行初始化
    head->next = NULL;
    return head;
}

//入链式队列
linkQueue_t * enQueue(linkQueue_t * rear, int data) {
    //1、用节点包裹入队元素
    linkQueue_t * temp = (linkQueue_t *)malloc(sizeof(linkQueue_t));
    temp->data = data;
    temp->next = NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next = temp;
    //3、rear指向新节点
    rear = temp;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

//出链式队列
linkQueue_t * deQueue(linkQueue_t * head, linkQueue_t * rear) {
    if (head->next == NULL) {
        /* 头节点后继为空即头尾相等 */
        printf("队列为空");
        return rear;
    }
    //通过 head 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
    linkQueue_t * p = head->next;
    printf("%d ",p->data);
    //将 p 节点（即要出队的队头节点）从链表中摘除
    head->next = p->next;
    //节点 p是尾节点，删除后头尾节点重合
    if(rear == p) {
        rear = head;
    }
    //释放节点 p
    free(p);
    return rear;
}

int main(int argc, char * argv[]) {
    //创建头结点
    linkQueue_t * queue, * head, * rear;
    queue = head = rear =  initQueue();
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    for(int i = 1; i < 5; i++) {
        rear = enQueue(rear, i);
    }
    //入队完成，所有数据元素开始出队列
    for(int i = 1; i < 6; i++) {
        rear = deQueue(head, rear);
    }
    return 0;
}